package com.leetcode;

import java.util.HashSet;

/**
 * <p>
 * 【题目】：leetcode第03题：参考：https://leetcode-cn.com/problems/programmable-robot/
 * 力扣团队买了一个可编程机器人，机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command，机器人就会无限循环这条指令的步骤进行移动。指令有两种：
 * U: 向y轴正方向移动一格
 * R: 向x轴正方向移动一格。
 * 不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。
 * 给定终点坐标(x, y)，返回机器人能否完好地到达终点。如果能，返回true；否则返回false。
 * <p>
 * 示例 1：
 * 输入：command = "URR", obstacles = [], x = 3, y = 2
 * 输出：true
 * 解释：U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。
 * <p>
 * 示例 2：
 * 输入：command = "URR", obstacles = [[2, 2]], x = 3, y = 2
 * 输出：false
 * 解释：机器人在到达终点前会碰到(2, 2)的障碍物。
 * <p>
 * 示例 3：
 * 输入：command = "URR", obstacles = [[4, 2]], x = 3, y = 2
 * 输出：true
 * 解释：到达终点后，再碰到障碍物也不影响返回结果。
 * </p>
 *
 * @author: Sunny
 * @date: 2021/3/2
 * @version: v1.0.0
 */
public class RobotsAdventure {

    public static void main(String[] args) {
        // command = "URR", obstacles = [[2, 2]], x = 3, y = 2
        int[][] value = {{4, 2}};
        System.out.println(robot("URR", value, 3, 2));
    }

    /**
     * 限制：
     * 2 <= command的长度 <= 1000
     * command由U，R构成，且至少有一个U，至少有一个R
     * 0 <= x <= 1e9, 0 <= y <= 1e9
     * 0 <= obstacles的长度 <= 1000
     * obstacles[i]不为原点或者终点
     *
     * @return
     */
    public static boolean robot(String command, int[][] obstacles, int x, int y) {
        HashSet<Point> cnt = new HashSet<>();
        for (int[] it : obstacles) {
            cnt.add(new Point(it[0], it[1]));
        }
        int s = 0, e = 0;
        HashSet<Point> path = new HashSet<>();
        path.add(new Point(0, 0));
        for (char c : command.toCharArray()) {
            if (c == 'U') {
                e++;
            } else {
                s++;
            }
            Point cur = new Point(s, e);
            if (cnt.contains(cur)) {
                return false;
            }
            path.add(cur);
        }
        for (Point obs : cnt) {
            if (!(obs.x <= x && obs.y <= y)) {
                continue;
            }
            int step = Math.min(obs.x / s, obs.y / e);
            int curx = obs.x - step * s;
            int cury = obs.y - step * e;
            if (path.contains(new Point(curx, cury))) {
                return false;
            }
        }
        int step = Math.min(x / s, y / e);
        int curx = x - step * s;
        int cury = y - step * e;
        return path.contains(new Point(curx, cury));
    }

    static class Point {
        int x, y;

        Point(int xx, int yy) {
            x = xx;
            y = yy;
        }

        @Override
        public boolean equals(Object obj) {
            Point o = (Point) obj;
            return o.x == this.x && o.y == this.y;
        }

        @Override
        public int hashCode() {
            return x + y;
        }
    }

}

















